package algorithm.sort;

/**
 * @author xutao
 * created 2020/3/16 13:42
 */
public class ShellSort implements Sort {
    @Override
    public String name() {
        return "希尔排序";
    }

    @Override
    public void sort(Integer[] arr) {
        int length = arr.length;
//        //增量减半循环
        for (int gap = length / 2; gap > 0; gap /= 2) {
//            //每个增量下gap个分组
            for (int group = 0; group < gap; group++) {
//                //每个分组元素的循环
                for (int i = group + gap; i < length; i += gap) {
                    for (int j = i; j > group; j -= gap) {
                        if (arr[j] < arr[j - gap]) {
                            swap(arr,j,j-gap);
                        } else {
                            break;
                        }
                    }
                }
            }
        }

    }


}
